#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
/*
 * @lc app=leetcode.cn id=30 lang=cpp
 *
 * [30] 串联所有单词的子串
 */

// @lc code=start
class Solution {
public:
    // 最朴素的Map + 滑动窗口
    // vector<int> findSubstring(string s, vector<string>& words) {
    //     unordered_map<string, int> counter;
    //     for (int i = 0; i < words.size(); i++) counter[words[i]]++;
    //     int ws = words[0].size(), cs = words.size();
    //     vector<int> res;
    //     for (int i = 0; i + ws * cs - 1 < s.size(); i++) {
    //         unordered_map<string, int> temp;
    //         for (int j = 0; j < ws * cs; j += ws) {
    //             string x = s.substr(i + j, ws);
    //             temp[x]++;
    //         }
    //         if (temp == counter) res.push_back(i);
    //     }
    //     return res;
    // }

    // Map + 双指针
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> counter;
        for (int i = 0; i < words.size(); i++) counter[words[i]]++;
        int ws = words[0].size(), cs = words.size();
        vector<int> res;
        for (int i = 0; i < ws; i++) {
            int l = i, r = i;
            unordered_map<string, int> temp;
            while (r < s.size()) {
                string x = s.substr(r, ws);
                temp[x]++;
                r += ws;
                if (counter.count(x) == 0) {
                    temp.clear(); l = r;
                    continue;
                }
                while (temp[x] > counter[x]) {
                    string m = s.substr(l, ws);
                    temp[m]--; l += ws;
                }
                if (temp.size() == counter.size() && temp == counter) res.push_back(l);
            }
        }
        return res;
    }
};
// @lc code=end

